package sort;

/**
 * 插入排序
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] nums = new int[]{1,5,8,2,3,9,4};
        System.out.println("从小到大排序后的结果是:");
        int[] numbers = insert(nums);
        for(int i=0;i<numbers.length;i++){
            System.out.print(numbers[i]+" ");
        }
    }

    /**
     * 1.将一个具有n个元素的待排序数列分成两个子数列，一个有序和一个无序。
     * 2.刚开始，我们将左边第一个元素看成一个有序数列，右边n-1个元素看成无序数列。
     * 3.从右边无序数列中取出一个元素，在已排序数列中从后往前扫描（比较），找到相应的位置并插入，使插入后有序数列仍然有序。
     * 4.重复第3步，直到完成整个排序过程。
     * @param nums
     * @return
     */
    public static int[] insert(int[] nums){
        for(int i=1;i<nums.length;i++){
            int temp = nums[i];
            int t = i-1;
            while (t>=0&&nums[t]>temp){
                nums[t+1] = nums[t];
                t--;
            }
            nums[t+1] = temp;
        }
        return nums;
    }

}
